/*********************
*k[i]: 单词i, i=1->n
*p[i]: k[i]的检索概率, i=1->n
*d[i]: 表示键值在k[i]到k[i+1]之间的所有单词
*q[i]: k[i]到k[i+1]之间的单词(d[i])检索概率, i=0->n, q[0]表示所有键值小于k[1]的
*   单词的概率,q[n]表示所有键值大于k[n]的单词的概率
*e[i][j]: d[i-1],k[i..j],d[j]之间单词构成最有搜索树的搜索代价, 1<=i<=j<=n
*w[i][j]: e[i][j]所对应的树各节点深度加1(加了个虚父节点)时所增加的搜索代价
*e和w的递推式要相互配合
*e[i][j] =  {
*   max(r=i->j)e[i,r-1]+e[r+1,j]+p[r]+w[i][r-1]+w[r+1][j] =
*   max(r=i->j)e[i,r-1]+e[r+1,j]) + w[i][j]   1<=i<=n, j>=i  (1)
*   q[j] j=i-1, 1<=i<=n+1 //这里是为了方便计算(1), 空子树的代价
*}
*w[i][j] = {
*   sigma(r=i->j)p[r] + sigma(r=i-1->j)q[r] =
*       w[i][j-1] + p[j] + q[j]  n>=j>=i>=1   (2)
*   q[j]   j=i-1, 1<=i<=n+1 //方便计算(2), 空子树增加的代价
*}
*四边形不等式优化
*证明w满足QI(四边形不等式), 即
    w(i,j)+w(i',j')<=w(i,j')+w(i',j), i<=i'<=j<=j' (3)
*只需证明当i<i'<=j<j'时(3)成立即可
*注意到w(i,j)=w(i,r)+w(r+1,j)-q(r), i<=r<=j (4)
*借助(4)用j拆分w(i',j'),w(i,j'),待人(3)转化得到
*  w(i,j)+w(i',j)+w(j+1,j')-q(j)<=w(i,j)+w(j+1,j')-q(j)+w(i',j), 显然成立
*所以w满足QI
*显然w(i,j)具备单调性：w(i,j)<=w(i',j') if (i,j) in (i',j')
*证e满足QI: e(i,j)+e(i',j')<=e(i,j')+e(i',j),   i<=i'<=j<=j'  (5)
*当i=i'或j=j'时(5)显然成立
*证当i<i'<=j<j'时(5)成立    (8) 
*定义Ke(i,j)=min{k|e(i,j)=e(i,k-1)+e(k+1,j)+w(i,j)}, i<=k<=j
*另x=Ke(i,j'), y=Ke(i',j) 
*case1) x=y 可首先将拆分(去i，i')转化为 e(x+1,j)+e(y+1,j')<=e(x+1,j')+e(y+1,j), 显然成立。  
*case2) x<y, 将(5)拆分(去i，i')转化为 e(x+1,j)+e(y+1,j')<=e(x+1,j')+e(y+1,j) (6)
*case2-1) y=j, (6)转化为e(x+1,j)+e(j+1,j')<=e(x+1,j')+q[j]  (7), 另k=Ke(x+1,j')
*case2-1-1) k=j, 以k=j拆e(x+1,j')去e(j+1,j')后(7)转化为
*   e(x+1,j)<=e(x+1,j-1)+w(x+1,j')+q[j]，继续以j拆e(x+1,j)去e(x+1,j-1)后得到
*   e(j+1,j)+w(x+1,j)<=w(x+1,j')+q[j], 显然成立
*case2-1-2) k<j, 以k同时拆e(x+1,j),e(x+1,j')去x后(7)暴力转化为
*   e(k+1,j)+e(j+1,j')<=e(k+1,j')+q[j], 注意到该问题是case2-1)的递归子问题。且参
*   数间差更小(k>x, x+1<k+1<=j<j+1<j'), 可以继续递归下去，直到不能再进入该分支。
*case2-1-3 k=j+1, 以k=j+1拆e(x+1,j')去e(x+1,j),该分支和case2-1-1对称。
*case2-1-4 k>j+1, 以k同时拆e(j+1,j'),e(x+1,j')去j',该分支和case2-1-2对称。
*case2-2) y<j, 此时有i<x+1<y+1<=j<j', 该分支为(8)的递归子问题，且参数间差更小
*   可以继续递归下去，直到不能再进入该分支。
*case3) x>y, 该分支和case2)对称。
*宗上e符合四边形不等式
*所以可对e采用四边形不等式优化
*s[i,j]=Ke(i,j) s[i,j-1]<=s[i,j]<=s[i+1,j], i<j
*w[i,j] = {
*   q[i-1]+p[i]+q[i]    i=j>=1
*   w[i,j-1]+p[j]+q[j]   1<=i<j<=n
*}
*e[i,j] = {
*   w[i,i]+q[i-1]+q[i]    i=j
    w[i,j]+min{e[i,k-1]+e[k+1,j]}, i<=s[i,j-1]<=k<=s[i+1,j]<=j, 1<=i<j<=n   (9)
    q[j], j=i-1, 方便(9)
*}
**********************/
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

typedef vector<vector<int>> IVV;
typedef vector<vector<double>> DVV;
#define MAXINT (((unsigned)-1)>>1)
//计算最小代价，并记录最优结构
//root[i][j]: 最优子树k[i..j]的根节点，i=1->n-1, j=i->n-1
double optimal_bst(double p[], double q[], int n, IVV &root) {
    DVV e(n+2, vector<double>(n+1));
    DVV w(n+2, vector<double>(n+1));
    root.resize(n+1);
    int i, j;
    for(j=0; j<=n; j++) {
        w[j+1][j] = e[j+1][j] = q[j];
        root[j].resize(n+1);
    }
    root[n].resize(n+1);
    int l; //i,j差
    int r; //当前分割点
    double tmin; //记录当前代价
    for(l=0; l<n; l++) {
        for(i=1,j=i+l; j<=n; i++,j++) {
            //r=i
            e[i][j] = e[i][i-1]+e[i+1][j]; 
            root[i][j] = i;
            for(r=i+1; r<=j; r++) {
                tmin = e[i][r-1]+e[r+1][j];
                if(tmin<e[i][j])  {
                    e[i][j]=tmin;
                    root[i][j] = r;
                }
            }
            w[i][j] = w[i][j-1]+q[j]+p[j];
            e[i][j] += w[i][j];
        }
    }
    return e[1][n];
}

double qi_optimal_bst(double p[], double q[], int n, IVV &root) {
    DVV e(n+2, vector<double>(n+1));
    DVV w(n+2, vector<double>(n+1));
    root.resize(n+1); //s[i][j]
    int i, j;
    for(i=1; i<=n; i++) {
        w[i][i] = q[i-1]+p[i]+q[i];
        e[i][i] = w[i][i]+q[i-1]+q[i];
        e[i][i-1] = q[i-1];
        root[i].resize(n+1);
        root[i][i] = i;
    }
    e[n+1][n] = q[n];
    int l; //i,j差
    int r; //当前分割点
    double tmin;
    for(l=1; l<n; l++) {
        for(i=1,j=i+l; j<=n; i++,j++) {
            e[i][j] = MAXINT;
            for(r=root[i][j-1]; r<=root[i+1][j]; r++) {
                tmin = e[i][r-1]+e[r+1][j];
                if(tmin<e[i][j])  {
                    e[i][j]=tmin;
                    root[i][j] = r;
                }
            }
            w[i][j] = w[i][j-1]+q[j]+p[j];
            e[i][j] += w[i][j];
        }
    }
    return e[1][n];
    
}

void construct_optimal_bst_core(IVV &root, int i, int j, int pid);
//打印树的父子关系(包括伪节点di:空节点）
void construct_optimal_bst(IVV &root) {
    construct_optimal_bst_core(root, 1, root.size()-1, -1);
}
void construct_optimal_bst_core(IVV &root, int i, int j, int pid) {
    if(i>j) {
        if(pid==i) printf("d%d为k%d的左孩子\n", pid-1, pid);
        else printf("d%d为k%d的右孩子\n", pid, pid);
        return;
    }
    int r = root[i][j];
    if(pid==-1) {
        printf("k%d为根\n", r);
    }else {
        if(r<pid) printf("k%d为k%d的左孩子\n", r, pid);
        else printf("k%d为k%d的右孩子\n", r, pid);
    }
    construct_optimal_bst_core(root, i, r-1, r);
    construct_optimal_bst_core(root, r+1, j, r);
}

int main(void) {
    double p[] = {0, 0.15, 0.10, 0.05, 0.10, 0.20};
    double q[] = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10};
    IVV root; //记录e[i][j]对应树的根
    printf("最小搜索代价为: %f\n", optimal_bst(p, q, 5, root));
    printf("(QI)最小搜索代价为: %f\n", qi_optimal_bst(p, q, 5, root));
    printf("最优结构：\n");
    construct_optimal_bst(root);
    double p2[] = {0, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12};
    double q2[] = {0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05};
    printf("最小搜索代价为: %f\n", optimal_bst(p2, q2, 6, root));
    printf("(QI)最小搜索代价为: %f\n", qi_optimal_bst(p2, q2, 6, root));
    printf("最优结构：\n");
    construct_optimal_bst(root);
    return 0;
}
